package 栈;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public class No94二叉树的中序遍历 {

    /**
     * 先吃左再吃自己再吃右
     * 先到最左,然后再开吃
     */
    public static List<Integer> inorderTraversal(TreeNode root) {

        Stack<TreeNode> stack=new Stack<>();
        TreeNode thisNode=root;
        List<Integer> list=new ArrayList<>();

        while (!stack.isEmpty()||thisNode!=null){
            if(thisNode!=null){
                stack.add(thisNode);
                thisNode=thisNode.left;//去往最左
            }else{
                //最左已经抵达,开始吞入最左
                thisNode = stack.pop();
                //无论如何都要吃掉这个左
                list.add(thisNode.val);
                if(thisNode.right==null){
                    //右边为空了,就不管了,等下栈吐出
                    thisNode=null;
                }else{
                    //右边不为空,加入右边
                    thisNode=thisNode.right;
                }
            }

        }
        return list;
    }

    public static void main(String[] args) {
        /**
         *     1
     *     2       3
 *     4     5   6    7
*        44
     */

        List<Integer> list = inorderTraversal(TreeNode.getNode());
        System.out.println(JSON.toJSONString(list));
        ReentrantLock reentrantLock=new ReentrantLock();
    }


}
